package window;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
import utils.ComparatorUtil;
public class Ex239 {
    //思考错了方向，应该使用单调递减栈
    //二：错误的认为队列应该和窗口同步，实际上没有实际的关联，窗口只是为最后的结果判断提供依据
    //三：最重要的步骤：当出现大元素时，需要将小元素全部出栈
    class Solution1 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int lo = 0, hi = 0, len = nums.length;
            if (k == 1) return nums;
            Deque<Integer> deque = new ArrayDeque<>(k);
            List<Integer> res = new ArrayList<>();

            deque.offerLast(nums[0]);
            for (int i = 1; i < k - 1; i++) {
                if (nums[i] > deque.peekLast()) {
                    deque.offer(i);
                }
                hi++;
            }

            while (hi < len - 1) {
                hi++;
                if (!deque.isEmpty() && (hi - deque.peekFirst() >= k)) {
                    deque.pollFirst();
                    if (deque.isEmpty()) {
                        int idx = lo;
                        while ((deque.isEmpty() || nums[deque.peekLast()] < nums[idx]) && idx < hi) deque.offerLast(idx++);
                    }
                }
                if (nums[hi] > nums[deque.peekLast()]) deque.offerLast(hi);
                res.add(nums[deque.peekLast()]);
                lo++;
            }
            
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    //单调递减栈，实际存储的是下标  错误代码
    class Solution2 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int lo = 0, hi = 0, len = nums.length;
            if (k == 1) return nums;
            Deque<Integer> deque = new ArrayDeque<>(k);
            List<Integer> res = new ArrayList<>();

           
            //初始化队列的过程：hi右移，lo不动
            while (hi - lo < k - 1 && hi < len) {
                if (deque.isEmpty() || nums[hi] < nums[deque.peekLast()]) {
                    deque.offerLast(hi);
                }
                hi++;
            }

            while (hi < len) {
                int cur = nums[hi];
                while (nums[deque.peekLast()] < cur) { //当当前元素大于队尾元素，一直弹出队尾，直到大于cur，保证最左元素是最大值
                    deque.pollLast();
                }
                deque.offerLast(hi);
                if (deque.peekFirst() < lo) { //当前最大值已经不在窗口中
                    deque.pollFirst();
                }

                //当窗口大小已经达到k时，才进行测速
                if (hi - lo == k - 1) {
                    res.add(nums[deque.peekFirst()]);
                    lo++;
                }
            }

            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

     //单调递减栈，实际存储的是下标 抄来的
     class Solution3 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int lo = 0, hi = 0, len = nums.length;
            if (k == 1) return nums;
            Deque<Integer> deque = new ArrayDeque<>(k);
            List<Integer> res = new ArrayList<>();

            for (int i = 0; i < nums.length; i++) {
                while (!deque.isEmpty() && (nums[deque.peekLast()] <= nums[i])) deque.pollLast();
                deque.offer(i);
                if (deque.peekFirst() <= i - k) deque.pollFirst();
                if (i >= k - 1) res.add(nums[deque.peekFirst()]);
            }

            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int lo = 0, hi = 0, len = nums.length;
            if (k == 1) return nums;
            Deque<Integer> deque = new ArrayDeque<>(k);
            List<Integer> res = new ArrayList<>();

            for (int i = 0; i < nums.length; i++) {
                while (!deque.isEmpty() && (nums[deque.peekLast()] <= nums[i])) deque.pollLast();
                deque.offer(i);
                if (deque.peekFirst() <= i - k) deque.pollFirst();
                if (i >= k - 1) res.add(nums[deque.peekFirst()]);
            }

            return res.stream().mapToInt(Integer::valueOf).toArray();
        }

        public int[] rightMethod(int[] nums, int k) {
            if (k == 1) return nums;
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i <= nums.length - k; i++) {
                int hi = i + k - 1, max = nums[i];
                for (int j = i + 1; j <= hi; j++) {
                    max = Math.max(max, nums[j]);
                }
                res[i] = max;
            }
            return res;
        }
    }


    @Test
    public void test2() {
        final int max = 100;
        final int size = 10;
        final int times = 50000;
        Solution s = new Solution();
        Solution1 s1 = new Solution1();
        Random random = new Random();
        for (int i = 0; i < times; i++) {
            int[] nums = ComparatorUtil.arrayComparator.generateRandomArray(size, max);
            int[] nums1 = ComparatorUtil.arrayComparator.arrayCopier(nums);
            int[] nums2 = ComparatorUtil.arrayComparator.arrayCopier(nums);
            int k = (int)Math.random() * (nums.length) + 1;
            int[] res1 = s1.maxSlidingWindow(nums, k);
            int[] res2 = s.rightMethod(nums1, k);
            boolean result;
            if (!(result = ComparatorUtil.arrayComparator.isArrayEqual(nums1, nums))) {
                System.out.println("fucked!");
                System.out.println(Arrays.toString(nums2));
            }
        }
        System.out.println("nice!");
    }
    @Test
    public void test() {
        Solution s = new Solution();
        // int[] nums = {1,3,-1,-3,5,3,6,7};
        int[] nums = ArrayGenerator.getArray(100, 100);
        System.out.println(Arrays.toString(nums));
        int[] res = s.maxSlidingWindow(nums, 5);
        System.out.println(Arrays.toString(res));
        System.out.println(Arrays.toString(s.rightMethod(nums, 5)));
    }


    /* 
    
            while (hi < len - 1) {
                while (hi - lo < k - 1) {
                    hi++;
                    if (!deque.isEmpty() && (hi - deque.peekFirst() >= k)) {
                        deque.peekFirst();
                        //若队列因此为空
                        int idx = lo;
                        while ((deque.isEmpty() || deque.peekLast() < nums[idx]) && idx < hi) deque.offerLast(nums[idx++]);
                    }
                    if (deque.isEmpty() || nums[hi] > nums[deque.peekLast()]) {
                        deque.offerLast(hi);
                    }
                }
                res.add(deque.peekLast());
                lo++;
            }

    
    */
}
